package Algorithm.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

//骑士周游问题/马踏棋盘算法
public class HoresChessboard {
	//棋盘的 列数
	private static int X;
	//行数
	private static int Y;

	//创建一个数组，标记棋盘各个位置是否被访问过
	private static Boolean[] isVisited;

	//表示是否棋盘的所有位置都被访问
	private static boolean isfinished;

	public static void main(String[] args) {
		X = 6;
		Y = 6;
		//马初始的行号，从 1 开始
		int row = 5;
		//列号
		int column = 5;

		//创建棋盘
		int[][] chessboard = new int[X][Y];
		isVisited = new Boolean[X * Y];
		for (int i = 0; i < isVisited.length; i++) {
			isVisited[i] = false;
		}


		long start = System.currentTimeMillis();
		traversalChessboard(chessboard, row - 1, column - 1, 1);
		long end = System.currentTimeMillis();
		System.out.println("共耗时：" + (end - start) / 1000 + "秒");

		for (int[] rows : chessboard) {
			for (int steps : rows) {
				System.out.print(steps + " ");
			}
			System.out.println();
		}

	}

	//=====核心==========================

	/**
	 * 完成骑士周游问题的算法
	 *
	 * @param chessboard 棋盘
	 * @param row        马当前位置的行号（从 0 开始）
	 * @param column     马当前位置的列号（从 0 开始）
	 * @param step       马当前走到第几步，初始为 1
	 */
	public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
		//标记该位置是第几步
		chessboard[row][column] = step;
		//标记该位置已被访问
		isVisited[row * X + column] = true;
		//获取当前位置可以走的下一个集合
		ArrayList<Point> ps = next(new Point(column, row));
		//对 ps 所有元素下一步可选位置的数目，进行 非递减 排序
		sort(ps);
		//遍历可以走的集合
		while (!ps.isEmpty()) {
			//取出下一个可以走的位置
			Point p = ps.remove(0);
			//判断该点是否已经被访问
			if (!isVisited[p.y * X + p.x]) {
				//若成立，则未被访问过，继续
				traversalChessboard(chessboard, p.y, p.x, step + 1);
			}
		}

		//判断马是否完成，使用 step 和 应该走的步数(X * Y) 进行比较，
		//若没有达到数量，则表示没有完成，将整个棋盘置为 0
		//step < X * Y 若成立，表示：1.棋盘到目前为止没走完；2.棋盘已走完是在回溯过程中
		if (step < X * Y && !isfinished) {
			chessboard[row][column] = 0;
			isVisited[row * X + column] = false;
		} else {
			isfinished = true;
		}
	}

	//================================================

	/**
	 * 根据当前的位置（point对象），计算 🐎 还能走那些位置，并放入到一个集合中
	 *
	 * @param curPoint
	 * @return
	 */
	public static ArrayList<Point> next(Point curPoint) {
		//创建一个 ArrayList
		ArrayList<Point> ps = new ArrayList<>();
		//创建一个 Point
		Point p1 = new Point();


		//====马走的策略=========================================
		//表示 马走的日字（向左走2列，向上走1行）
		if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
			ps.add(new Point(p1));
		}

		//表示 马走的日字（向左走1列，向上走2行）
		if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
			ps.add(new Point(p1));
		}
		//表示 马走的日字（向右走1列，向上走2行）
		if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
			ps.add(new Point(p1));
		}
		//表示 马走的日字（向右走2列，向上走1行）
		if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
			ps.add(new Point(p1));
		}
		//表示 马走的日字（向右走2列，向下走1行）
		if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
			ps.add(new Point(p1));
		}
		//表示 马走的日字（向右走1列，向下走2行）
		if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
			ps.add(new Point(p1));
		}
		//表示 马走的日字（向左走1列，向下走2行）
		if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
			ps.add(new Point(p1));
		}
		//表示 马走的日字（向左走2列，向下走1行）
		if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
			ps.add(new Point(p1));
		}
		return ps;

	}

	//根据当前这步的 所有的 下一步的可选择的位置数目进行 非递减排序
	//先选择再下一步可选位置最少的位置，来减少回溯的次数
	public static void sort(ArrayList<Point> ps) {
		//重写 sort 方法
		ps.sort(new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) {
				//获取 o1、o2 点的下一步的所有可选位置数
				int count1 = next(o1).size();
				int count2 = next(o2).size();
				//非递减排序
				if (count1 < count2) {
					return -1;
				} else if (count1 == count2) {
					return 0;
				} else {
					return 1;
				}
			}
		});
	}
}
